// https://leetcode.cn/problems/maximum-swap/
// Created by ade on 2022/9/13.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    // 思路：单调栈思维，双指针
    // 先找出left点，left:第一个右侧值大于左侧值的地方
    // 找出right点，right只要比前一个right要大，right就更新
    // left和最大的right的位置不断对比，只要left的值 小于 right的值，left--
    // 交换left和right的值

    int maximumSwap(int num) {
        if (num < 10) return num;
        string numS = to_string(num);
        int len = numS.size();
        int left = 0, right = 0;
        int i = 1;
        while (i < len && numS[i - 1] >= numS[i]) i++;
        if (i == len) return num;
        left = i - 1;
        right = i;
        while (i < len) {
            if (numS[i] >= numS[right]) {
                right = i;
            }
            i++;
        }
        while (left > 0 && numS[right] > numS[left - 1]) {
            left--;
        }
        swap(numS[left], numS[right]);
        return stoi(numS);
    }
};

int main() {
    Solution so;
    int num = 98368;
    cout << so.maximumSwap(num);
    return 0;
}